package dynamicStudy;

public class DynamicStudy05 {

    /**
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * 总结：该题目的边界在对称轴上，通过对称轴进行遍历
     * 总结：用二维数组解决最优问题，转化一下，枚举出来所有可能的字符串，然后判断是否是回文字符串，然后找出长度最长字符串。
     *
     * 用二维数组解决存在性问题，边界位于对称轴，
     * 分析：对于大于2的字符串：
     * @param args
     */
    public static void main(String[] args) {

    }

    //方法一：暴力破解法，列举出所有的子串，判断是否为回文串，然后保存最长的回文串
    public static String longestPalindrome01(String s) {
        if (s == null || "".equals(s)) {
            return s;
        }
        //记录最大长度
        int maxLen = 0;
        //记录字符串
        String ans = "";
        int len = s.length();
        //遍历不同长度的字符串
        for (int i = 1; i <= len; i++) {
            //从第一个开始不停寻找
            for (int j = 0; j < len; j++) {
                //尾索引为
                int last = j + i;
                if (last > len){
                    break;
                }
                //得到新生成的字符串
                String test = s.substring(j, last);
                if (isLongestPalindrome(test) && test.length() > maxLen){
                    ans = s.substring(j, last);
                    maxLen = ans.length();
                }
            }
        }
        return ans;
    }

    public static boolean isLongestPalindrome(String s){
        int len = s.length();
        for (int i = 0; i < len/2; i++){
            if (s.charAt(i) != s.charAt(len - i - 1)){
                return false;
            }
        }
        return true;
    }


    //方法二：动态规划，保存暴力破解法中的中间过程，减小时间复杂度
    public static String longestPalindrome(String s){
        if (s==null || "".equals(s))
            return s;
        int len = s.length();
        //记录最大长度和起始位置
        int begin = 0;
        int maxLen = 1;
        //可以用暴力枚举解决这个问题，但是可以把暴力枚举中的一些结果保存起来，这就是动态规划。
        //所以这道题就是把最优解问题转化为了存在性问题,用行代表开始索引，列代表结束索引。
        boolean[][] dp = new boolean[len][len];
        //初始化边界值，所有只有一个字符的子串都是回文，有两个三个的子串的，子要和第一个相同及回文，不同不回文
        for (int i = 0; i < len; i++){
            //其他情况可以放到循环体中进行初始化
            dp[i][i] = true;
        }
        //需要斜向进行遍历节点，初始字符串长度为2，依次斜向进行遍历
        for (int L = 2; L <= len; L++){
            for (int i = 0; i < len; i++){
                //列数为当前行数加上
                int j = i + L -1;
                if (j > len - 1){
                    break;
                }
                //如果头尾不相等，肯定不是回文字串
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                } else { //若不相等，第二斜行需要进行初始化，第三斜行和第二斜行一样，其他部分使用转义方程
                    if (L< 4){
                        dp[i][j] = true;
                    } else {
                        //转换方程很重要，怎么确定的,上一步
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j]&&L>maxLen){
                    maxLen = L;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    //方法三：中心扩展法，从边界向外不断扩展
    public static String longestPalindrome02(String s){
        if (s == null || s.length() < 1){
            return s;
        }
        int start = 0, end = 0;
        int len = s.length();
        for (int i = 0; i < len; i++){
            //判断以边界为中心，可以回文多少
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);
            int len3 = Math.max(len1, len2);
            if (len3 > end - start + 1){
                start = i - (len3 - 1)/2;
                end = i + len3/2;
            }
        }
        return s.substring(start, end + 1);
    }

    public static int expandAroundCenter(String s, int left, int right){
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }
}
